#include "glob.h"
#include "freeMem.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/*freeMem:
 *
 * author: Will Lamond
 *
 * A linked list of structures to keep track of free memory.
 *
 */

/*add a node of free memory.  Supply the base and limit memory location of the process that
 *is being removed */

int addNode(FREEMEMLIST *list, int base, int end) {
	MEMNODE *new = malloc(sizeof(MEMNODE));
	if (new) { //check to see if the malloc failed.
		MEMNODE *temp = list->head;
		//Check for the case where the new node is at the beginning of the list */
		if (base < temp->base) {
			//Check for the case where free memory nodes are contiguous.
			if (end == (temp->base - 1)) {
				new->base = base;
				new->end = temp->end;
				new->size = (new->end - (new->base - 1));
				new->next = temp->next;
				list->head = new;
				free(temp);
#ifdef DEBUG | DEBUG_FAULTS
				printf("Successfully deallocated space from %d to %d\n", base, end);
#endif
				return 1;
			}
			if (end > temp->base && end < temp->end) {
				new->base = base;
				new->end = temp->end;
				new->size = (new->end) - ((new->base) - 1);
				new->next = temp->next;
				list->head = new;
				free(temp);
#ifdef DEBUG | DEBUG_FAULTS
				printf("Successfully deallocated space from %d to %d\n", base, end);
#endif
				return 1;
			}
			//the case where the head node is now a new free memory node that is
			//not contiguous with the next free memory node, so it gets put in front
			//of the old head node.
			new->base = base;
			new->end = end;
			new->size = (end - (base - 1));
			new->next = temp;
			list->head = new;
#ifdef DEBUG | DEBUG_FAULTS
			printf("Successfully deallocated space from %d to %d\n", base, end);
#endif
			return 1;
		} else {
			MEMNODE *last = temp;
			//Keep looping until it finishes or doesn't find the proper node.
			//The result of the assignment gets evaluated to true if the next
			//node isn't null, false if it is null.
			temp = temp->next;
			while (temp) {
				if (base < temp->base) {
					if (end == (temp->base - 1)) {
						new->base = base;
						new->end = temp->end;
						new->size = (new->end - (new->base - 1));
						new->next = temp->next;
						last->next = new;
						free(temp);
#ifdef DEBUG | DEBUG_FAULTS
						printf("Successfully deallocated space from %d to %d\n", base, end);
#endif
						return 1;
					} else if (end > temp->base && end < temp->end) {
						new->base = base;
						new->end = temp->end;
						new->size = (new->end) - (new->base - 1);
						new->next = temp->next;
						free(temp);
#ifdef DEBUG | DEBUG_FAULTS
						printf("Successfully deallocated space from %d to %d\n", base, end);
#endif
						return 1;
					}
					new->base = base;
					new->end = end;
					new->size = (end - (base - 1));
					new->next = temp;
					last->next = new;
#ifdef DEBUG | DEBUG_FAULTS
					printf("Successfully deallocated space from %d to %d\n", base, end);
#endif
					return 1;
				} else {
					//The temp node wasn't the node we are looking for, so we shift everything by one
					last = temp;
				}

				temp = temp->next;
			}
			//Node wasn't added, so return -1 (shouldn't happen)
			return -1;
		}
	}

	return 1;
}

//removeNode: takes the base and limit values of a process and reorganizes free memory
int removeNode(FREEMEMLIST *list, int baseOfProc, int endOfProc) {
	MEMNODE *temp = list->head;
	//is the node we want to remove bounded by the head node?
	if (temp->base > baseOfProc && endOfProc <= temp->end) {
		//if it is, replace the current node with two nodes which describe the free memory.
		MEMNODE *new1 = malloc(sizeof(MEMNODE));
		MEMNODE *new2 = malloc(sizeof(MEMNODE));
		if (new1 && new2) { //check to see if either malloc failed.
			new1->base = temp->base;
			new1->end = (baseOfProc - 1);
			new1->size = (new1->end) - (new1->base);
			new2->base = (endOfProc + 1);
			new2->end = temp->end;
			new2->size = (new2->end) - (new2->base);
			new1->next = new2;
			new2->next = temp->next;
			list->head = new1;
			free(temp); //clean up pointer that is no longer used.
#ifdef DEBUG | DEBUG_FAULTS
			printf("Successfully allocated memory from %d to %d\n", baseOfProc, endOfProc);
#endif
			return 1;
		} else
			return -1;
	}
	//check for case where the head node is the node we want
	if (temp->base == baseOfProc) {
		//are the process and the node the same size?
		if (temp->end == endOfProc) {
			list->head = list->head->next;
			free(temp);
#ifdef DEBUG | DEBUG_FAULTS
			printf("Successfully allocated memory from %d to %d\n", baseOfProc, endOfProc);
#endif
			return 1;
		}
		//if they aren't, reorganize the head node.
		MEMNODE *new = malloc(sizeof(MEMNODE));
		new->base = (endOfProc + 1);
		new->end = temp->end;
		new->size = (new->end - new->base);
		new->next = temp->next;
		list->head = new;
		free(temp); //clean up the pointer that is no longer used.
#ifdef DEBUG | DEBUG_FAULTS
		printf("Successfully allocated memory from %d to %d\n", baseOfProc, endOfProc);
#endif
		return 1;
	} else {
		MEMNODE *last = temp;
		//search for the proper node
		while ((temp = temp->next)) {
			//is the node we want to remove bounded by the current node?
			if (temp->base > baseOfProc && endOfProc < temp->end) {
				//if it is, replace the current node with two nodes describing free memory.
				MEMNODE *new1 = malloc(sizeof(MEMNODE));
				MEMNODE *new2 = malloc(sizeof(MEMNODE));
				if (new1 && new2) { //check to see if either malloc failed
					new1->base = temp->base;
					new1->end = (baseOfProc - 1);
					new1->size = (new1->end - new1->base);
					new2->base = (endOfProc + 1);
					new2->end = temp->end;
					new2->size = (new2->end - new2->base);
					last->next = new1;
					new1->next = new2;
					new2->next = temp->next;
					free(temp);
#ifdef DEBUG | DEBUG_FAULTS
					printf("Successfully allocated memory from %d to %d\n", baseOfProc, endOfProc);
#endif
					return 1;
				} else
					return -1;
			}
			//is this the base you are looking for?
			if (temp->base == baseOfProc) {
				//are they the same size?
				if (temp->end == endOfProc) {
					last->next = temp->next;
					free(temp);
#ifdef DEBUG | DEBUG_FAULTS
					printf("Successfully allocated memory from %d to %d\n", baseOfProc, endOfProc);
#endif
					return 1;
				}
				//if not, reorganize the current node.
				MEMNODE *new = malloc(sizeof(MEMNODE));
				if (new) { //check to see if malloc failed.
					new->base = (endOfProc + 1);
					new->end = temp->end;
					new->size = (new->end - new->base);
					new->next = temp->next;
					last->next = new;
					free(temp);
#ifdef DEBUG | DEBUG_FAULTS
					printf("Successfully allocated memory from %d to %d\n", baseOfProc, endOfProc);
#endif
					return 1;
				} else
					return -1;
			}
			//Not the correct node, so shift over by one.
			last = temp;
		}
		//return that an error occured.
		return -1;
	}
}

/*initList: Initialize the free memory manager list. */
int initList(FREEMEMLIST **newList, int size) {
	*newList = malloc(sizeof(FREEMEMLIST));
	if (*newList == NULL) {
		printf("Error allocating memory.\n");
		return -1;
	}

	MEMNODE *new = malloc(sizeof(MEMNODE));
	if (new == NULL) {
		printf("Error allocating memory.\n");
		return -1;
	}
	new->base = 0;
	new->end = size;
	new->size = size;
	new->next = NULL;
	(*newList)->head = new;
	return 1;
}

/*initIterator: Initialize an iterator. */
int initIterator(LISTITERATOR *it, FREEMEMLIST *list) {
	if (it == NULL) {
		printf("Error allocating memory.\n");
		return -1;
	}
	(it)->list = list;
	(it)->curNode = list->head;
	return 1;
}

/*getNext: gets the next node and values from an iterator. */
int getNext(LISTITERATOR *it, int *base, int *end, int *size) {
	if (it->curNode == NULL) {
		*base = -1;
		*end = -1;
		*size = -1;
		return -1;
	} else {
		*base = (it->curNode->base);
		*end = (it->curNode->end);
		*size = (it->curNode->size);
		it->curNode = it->curNode->next;
		return 1;
	}
}

int FindFirstFit(FREEMEMLIST *ml, int size) {

	int err = -1;
	int base = -1;
	int end = -1;
	int nodeSize = -1;
	LISTITERATOR it;

	err = initIterator(&it, ml);
	if (err < 0) {
		printf("Failed to initialize iterator.\n");
		return -2;
	}

	while (getNext(&it, &base, &end, &nodeSize) > 0) {
		if (size <= nodeSize)
			return base;
	}
	return -1;
}

int FindBestFit(FREEMEMLIST *ml, int size) {
	int err = -1;
	int base = -1;
	int end = -1;
	int nodeSize = -1;
	int curBestBase = -1;
	int curBestSize = 999;
	LISTITERATOR *it = (LISTITERATOR*) malloc(sizeof(LISTITERATOR));;

	err = initIterator(it, ml);
	if (err < 0) {
		printf("Failed to initialize iterator 1.\n");
		return -2;
	}

	while (getNext(it, &base, &end, &nodeSize) > 0) {
		if (size <= nodeSize) {
			if (nodeSize < curBestSize) {
				curBestSize = nodeSize;
				curBestBase = base;
			}
		}
	}
	return curBestBase;
}
